class Solution {
public:
    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fis-unique-lcci%2F
    bool isUnique(string astr) //题目要求：如果你不使用额外的数据结构，会很加分。
    {
        int i = 0;
        int old;
        for(auto& c: astr)
        {
            old = i;
            i |= 1<<(c - 'a');
            if(i == old) return false;
        }
        return true;
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fmissing-number%2F
    int missingNumber(vector<int>& nums) //你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
    {
        int key = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            key ^= i + 1;
            key ^= nums[i];
        }   
        return key;
    }

    //https://leetcode.cn/problems/number-of-1-bits/
    int hammingWeight(int n) 
    {
        int count = 1;
        while(n = n & n - 1)//假设n:01011100 
                            // n- 1：01011011 (n&n-1)操作去掉了最右侧的1
        {
            count++;
        } 
        return count;
    }

    //https://leetcode.cn/problems/counting-bits/
    vector<int> countBits(int n) 
    {
        vector<int> v1(n + 1);
        for(int i = 1; i <= n; i++)
        {
            int count = 1;
            int num = i;
            while(num = num & num - 1)//与上题思想一致
            {
                count++;
            }
            v1[i] = count;
        }
        return v1;
    }

    //https://leetcode.cn/problems/hamming-distance/
    int hammingDistance(int x, int y) 
    {
        int count = 0;
        int num = x^y;
        while(num)
        {
            count++;
            num = num & num -1;
        }
        return count;
    }

    //https://leetcode.cn/problems/single-number/
    int singleNumber(vector<int>& nums) //找单身狗
    {
        int num = 0;
        for(auto i: nums)
        {
            num ^= i;
        }    
        return num;
    }

    //https://leetcode.cn/problems/single-number-iii/
    vector<int> singleNumber(vector<int>& nums) 
    {
        vector<int> v1(2);
        long long num = 0;//避免nums中只出现过1次的数是INT_MIN:(-2147483648)
        for(auto i: nums)//num：001001100  
        {                //-num:110110100(num取反再加1)
            num ^= i;
        }    
        int n = num & -num;//找出最右侧的1
        v1[0] = num;
        for(auto i: nums)
        {
            if(i & n) v1[0] ^= i;
        }
        v1[1] = num ^ v1[0];
        return v1;
    }

    //https://leetcode.cn/problems/sum-of-two-integers/submissions/680169819/
    int getSum(int a, int b) 
    {
        while(b != 0)
        {
            int num = a^b;
            int val = (a&b)<<1;//要进的位数
            a = num;
            b = val;
        }
        return a;
    }

    //https://leetcode.cn/problems/single-number-ii/
    int singleNumber(vector<int>& nums) 
    {
        int num = 0;
        for(int i = 0; i < 32; i++)//一位一位的去更改num中的值
        {
            int sum = 0;
            for(auto c: nums)
                if(((c >> i) & 1)) sum++;
            num |= ((sum % 3) << i);
        }
        return num;
    }

    //https://leetcode.cn/problems/missing-two-lcci/
    vector<int> missingTwo(vector<int>& nums) 
    {
        int i = nums.size() + 2;
        i ^= nums.size() + 1;
        for(int j = 0; j < nums.size(); j++)
        {
            i ^= nums[j];
            i ^= j+1;
        }
        vector<int> v1(2, i);
        i &= -i;
        for(int j = 0; j < nums.size(); j++)
        {
            if(nums[j] & i) v1[0] ^= (nums[j]);
            if(j + 1 & i) v1[0] ^= j + 1;
        }
        if(nums.size() + 2 & i) v1[0] ^= nums.size() + 2;
        if(nums.size() + 1 & i) v1[0] ^= nums.size() + 1;
        v1[1] ^= v1[0];
        return v1;
    }
};